import sys

class Solution(object):
    def maximumGap(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums)<2: return 0

        maxVal = max(nums)
        minVal = min(nums)
        dis = maxVal-minVal
        nBucket = len(nums)-1
        bucketSize = dis//nBucket if dis%nBucket==0 else dis//nBucket+1 
        if bucketSize==0: bucketSize=1
        
        minBucket = [sys.maxsize] * len(nums)
        maxBucket = [-sys.maxsize] * len(nums)

        for num in nums:
            i = (num-minVal)//bucketSize
            minBucket[i] = min(minBucket[i], num)
            maxBucket[i] = max(maxBucket[i], num)
        
        pre = -1
        gap = 0
        for i in range(len(nums)):
            if minBucket[i]==sys.maxsize or maxBucket[i]==-sys.maxsize: 
                continue
            if pre==-1:
                pre = i
                continue
            gap = max(gap, minBucket[i]-maxBucket[pre])
            pre = i
        return gap

print(Solution().maximumGap([1,100]))